// 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

// 如果数组中不存在目标值 target，返回 [-1, -1]。

// 进阶：

// 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
//  

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 执行用时：
// 8 ms
// , 在所有 C++ 提交中击败了
// 77.13%
// 的用户
// 内存消耗：
// 13.2 MB
// , 在所有 C++ 提交中击败了
// 91.08%
// 的用户

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<set>
using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        int l=0,r=nums.size()-1;
        while(l<r){
            int mid=(l+r)/2;
            if(nums[mid]<target){
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        if(nums.size()==0){
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        if(nums[r]!=target){
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        int temp_l = 0,temp_r=nums.size()-1;
        while(temp_l<l){
            int mid = (l+temp_l)/2;
            if(nums[mid]<target){
                temp_l=mid+1;
            }
            else{
                l=mid;
            }
        }        
        while(r<temp_r){
            int mid = (r+temp_r)/2;
            if(nums[mid]>target){
                temp_r=mid;
            }
            else{
                r=mid+1;
            }
        }
        res.push_back(l);
        if((r-1)<0 || nums[nums.size()-1]==target){
            res.push_back(r);
        }
        else{
            res.push_back(r-1);
        }
        return res;
    }
};